# 数据结构是相互之间存在着一种或多种关系的数据元素的集合、和该集合中数据元素之间的关系组成
# 数据结构就是设计数据以何种方式组织并存储在计算机中

# 逻辑结构划分
# 1.线性结构，这个结构当中所有的元素是存在一对一的关系
# 2.树结构，这个结构当中所有的元素存在一对多的关系
# 3.图结构，这个结构当中所有的元素存在多对多的关系

# 物理内存存储结构划分，数据在计算机内存中存储的实际形式


# 数组和链表

# 尝试回答下面几个问题
# 1，列表在内存中是如何存储数据的
# 2. 如何对对列表中的元素进行新增、删除、插入、修改、查找元素等操作
# 3. 这些操作的时间复杂度是多少
# 4. python 的列表是如何用代码实现的

# 他们在内存中都是连续存储的数据结构

# 数组的特点：
# 1.数组中所有的元素，存储的都是目标变量本身，且数组中所有的元素类型必须一致
# 2.数组的长度一旦在内存中被确定，就不能被修改
# 列表的特点：
# 1.列表在底层是基于数组实现的
# 2.列表中所有的元素存储的都是目标变量的内存地址，以保证所有的元素都是同一类型，从而实现同一个列表存储不同类型元素的能力
# 3.列表在初始化的时候会一次性申请一整块内存，当列表中持续增加元素超出初始申请内存大小的上限后，会再申请一块更大的内存，将原本的数据
# 复制到新地址上，然后删除老地址的数据，实现列表的可扩容

# 1.按照索引的方式查找或修改目标元素：O(1)
# 2.按照元素的值去进行查找：O(n)
# 3.新增元素：O(1)
# 4.删除元素：O(n)
# 5.插入元素：O(n)

# 链表
class Node:
    def __init__(self, item):
        self._item = item
        self._next = None

    def add_next_node(self, next_node):
        self._next = next_node

    def get_next_node(self):
        return self._next

    def get_item(self):
        return self._item

    def modify_item(self, new_item):
        self._item = new_item


class LinkedList:
    def __init__(self):
        self.start_node = None
        self._size = 0

    def __len__(self):
        """
        获取链表的长度，len()
        :return:
        """
        return self._size

    def __getitem__(self, item):
        """
        获取指定下标的元素值，a_list[1]
        :param item:
        :return:
        """
        return self._get_by_node(item).get_item()

    def is_empty(self):
        """
        判断链表是否为空
        :return:
        """
        return self.start_node is None

    def append(self, element):
        """
        新增一个元素
        :param element:
        :return:
        """
        node = Node(element)
        if self.is_empty():
            self.start_node = node
        else:
            last_node = self._get_by_node(self._size - 1)
            last_node.add_next_node(node)
        self._size += 1

    def pop(self):
        """
        弹出尾部元素
        :return:
        """
        if self.is_empty():
            return None
        if self._size == 1:
            last_node = self.start_node
            self.start_node = None
        else:
            last_node_before = self._get_by_node(self._size - 2)
            last_node = last_node_before.get_next_node()
            last_node_before.add_next_node(None)
        self._size -= 1
        return last_node.get_item()

    def delete(self, _index: int):
        """
        删除一个元素
        :param _index:
        :return:
        """
        if self.is_empty():
            raise IndexError("linked list is empty")
        if _index >= self._size:
            raise IndexError("Index is out of xxx")
        target_node_before = self._get_by_node(_index - 1)
        target_node = target_node_before.get_next_node()
        target_node_after = target_node.get_next_node()
        target_node_before.add_next_node(target_node_after)
        self._size -= 1

    def insert(self, _index: int, element):
        """
        插入一个新的元素
        :param _index:
        :param element:
        :return:
        """
        if self.is_empty():
            raise IndexError("linked list is empty")
        if _index >= self._size:
            raise IndexError("Index is out of xxx")
        node = Node(element)
        target_node_before = self._get_by_node(_index - 1)
        target_node = target_node_before.get_next_node()
        target_node_before.add_next_node(node)
        node.add_next_node(target_node)
        self._size += 1

    def _get_by_node(self, _index: int) -> Node:
        """
        获取指定下标的目标节点
        :param _index:
        :return:
        """
        if self.is_empty():
            raise IndexError("linked list is empty")
        if _index >= self._size:
            raise IndexError("Index is out of xxx")
        node = self.start_node
        i = 0
        while node.get_next_node() is not None and i < _index:
            node = node.get_next_node()
            i += 1
        return node


if __name__ == "__main__":
    a_list = [1, 2, 3, 4, 5]

    b_list = LinkedList()
    print(b_list.is_empty())

    b_list.append(1)
    b_list.append(2)
    b_list.append(3)
    b_list.append(4)
    b_list.append(5)
    print(len(b_list))
    print(b_list.is_empty())

    b_list.delete(2)
    print(len(b_list))

    b_list.insert(2, 6)
    print(len(b_list))

    while not b_list.is_empty():
        print(b_list.pop())
